function quickSort (start, end, arr = []) {
  if (start >= end) {
    return
  }
  let pivotIndex = partitionSingle(start, end, arr)
  quickSort(start, pivotIndex - 1, arr)
  quickSort(pivotIndex + 1, end, arr)
  return arr
}

function partitionSingle (start, end, arr = []) {
  const pivot = arr[start]
  let mark = start
  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      mark++
      [arr[mark], arr[i]] = [arr[i], arr[mark]]
    }
  }
  arr[start] = arr[mark]
  arr[mark] = pivot
  return mark
}

function quickSortThree (arr) {
  const size = arr.length
  if (size <= 1) {
    return arr
  }

  const left = [], center = [], right = [], pivot = arr[0]

  for (let i of arr) {
    if (i < pivot) {
      left.push(i)
    }
    if (i === pivot) {
      center.push(i)
    }
    if (i > pivot) {
      right.push(i)
    }
  }

  return [...quickSortThree(left), ...center, ...quickSortThree(right)]
}

const arr = [5, 1, 3, 6, 2, 4, 7, 8, 9]

console.time()
console.log(quickSort(0, arr.length - 1, arr))
console.timeEnd()


console.time()
console.log(quickSortThree(arr))
console.timeEnd()